#pragma once
#include <iostream>
#include <vector>
#include <cassert>

namespace close_hash
{
    const int default_capacity = 10;

    enum STATUS
    {
        EMPTY,
        DELETE,
        EXISTS
    };

    template <class T>
    struct HashData
    {
        T _val;
        STATUS _status;

        HashData() : _val(0), _status(EMPTY)
        {}
    };

    template <class T>
    class HashTable
    {
    public:
        HashTable() : _a(0)
        {}

        bool insert(const T& val)
        {
            int ret = Find(val);
            if(ret != -1)
                return false; //已经存在该值了
            //扩容
            if(_a * 10 >= _table.size() * 7)
            {
                int capacity = _table.empty() ? default_capacity : 2 * _table.size();
                HashTable<T> newHT;
                newHT._table.resize(capacity);
                for(int i = 0;i < _table.size();++i)
                {
                    if(_table[i]._status == EXISTS)
                        newHT.insert(_table[i]._val);
                }
                _table.swap(newHT._table);
            }
            int i = val % _table.size();
            while(_table[i]._status == EXISTS)
            {
                ++i;
                i %= _table.size();
            }
            _table[i]._status = EXISTS;
            _table[i]._val = val;
            ++_a;

            return true;
        }

        int Find(const T& val)
        {
            if(empty())
                return -1;
            int i = val % _table.size();
            int tmp = i;
            while(!(_table[i]._status == EXISTS && _table[i]._val == val))
            {
                ++i;
                i %= _table.size();
                if(i == tmp)
                    return -1;   //没找到
            }
            return i;
        }

        bool erase(const T& val)
        {
            assert(!empty());
            auto ret = Find(val);
            if(ret == -1)
                return false;    //没有找到要删除的数
            _table[ret]._status = DELETE;
            --_a;

            return true;
        }

        void Print()
        {
            assert(!empty());
            int n = _table.size();
            for(int i = 0;i < n;++i)
            {
                if(_table[i]._status == EXISTS)
                {
                    std::cout << _table[i]._val << " ";
                }
            }
            std::cout << std::endl;
        }

        bool empty() const
        {
            return _table.size() == 0;
        }

        ~HashTable()
        {}
    private:
        std::vector<HashData<T>> _table;   //哈希表
        int _a;                  //散列因子
    };
}

namespace link_hash
{
    const int default_capacity = 10;

    template <class K, class V>
    struct HashNode
    {
    public:
        std::pair<K, V> _val;
        HashNode<K, V>* _next;

        HashNode(const std::pair<K, V>& val) : _val(val), _next(nullptr)
        {}
    };

    template <class K, class V>
    class HashTable
    {
    public:
        HashTable() : _n(0)
        {}

        bool insert(const std::pair<K, V>& kv)
        {
            HashNode<K, V>* ret = find(kv.first);
            if(ret)
                return false;     //节点已经存在了
            if(_n * 7 >= _table.size() * 10)
            {
                int capacity = _table.empty() ? default_capacity : 2 * _table.size();
                std::vector<HashNode<K, V>*> newHT;
                newHT.resize(capacity);
                for(int i = 0;i < newHT.size();++i)
                {
                    newHT[i] = nullptr;
                }
                for(int i = 0;i < _table.size();++i)
                {
                    if(_table[i])
                    {
                        HashNode<K, V>* cur = _table[i];
                        while(cur)
                        {
                            int index = cur->_val.first % capacity;
                            HashNode<K, V>* Next = cur->_next;
                            cur->_next = newHT[index];
                            newHT[index] = cur;
                            cur = Next;
                        }
                    }
                    _table[i] = nullptr;
                }
                _table.swap(newHT);
            }
            int index = kv.first % _table.size();
            HashNode<K, V>* newnode = new HashNode<K, V>(kv);
            newnode->_next = _table[index];
            _table[index] = newnode;
            ++_n;

            return true;
        }

        HashNode<K, V>* find(const K& key)
        {
            if(_table.size() == 0)
                return nullptr;
            int index = key % _table.size();
            HashNode<K, V>* cur = _table[index];
            while(cur)
            {
                if(cur->_val.first == key)
                    return cur;
                cur = cur->_next;
            }
            return nullptr; //没找到
        }

        bool erase(const std::pair<K, V>& kv)
        {   
            HashNode<K, V>* ret = find(kv.first);
            if(ret == nullptr)
                return false;   //节点不存在
            int index = kv.first % _table.size();
            HashNode<K, V>* cur = _table[index];
            HashNode<K, V>* pre = nullptr;
            --_n;
            if(cur->_val.first == kv.first) //目标节点为头节点
            {
                _table[index] = cur->_next;
                delete cur;
                return true;
            }
            while(cur->_val.first != kv.first)
            {
                pre = cur;
                cur = cur->_next;
            }
            pre->_next = cur->_next;
            delete cur;

            return true;
        }

        void Print()
        {
            for(int i = 0;i < _table.size();++i)
            {
                if(_table[i])
                {
                    HashNode<K, V>* cur = _table[i];
                    while(cur)
                    {
                        std::cout << cur->_val.first << " : " << cur->_val.second << std::endl;
                        cur = cur->_next;
                    }
                }
            }
        }

        ~HashTable()
        {}
    private:
        std::vector<HashNode<K, V>*> _table;
        int _n;                           
    };
};